import java.util.LinkedList;
import java.util.Queue;

/**
 * Created by L.jp
 * Description:
 * User: 86189
 * Date: 2022-01-14
 * Time: 23:02
 */
 class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
public class Solution {
    /* public  static void getmaxDeepth(TreeNode root,int deepth,int max){
         if(root==null){
             //走到了没有节点的地方
             if(max<deepth){
                 //更新最大值
                 max = deepth;
             }
             return ;
         }
         //分别求左右子树的最大深度，每进入到一个子树，只要不为空，说明就有一层，所以加1
         getmaxDeepth(root.left,deepth+1,max);
         getmaxDeepth(root.right,deepth+1,max);
     }*/
    public int TreeDepth(TreeNode root) {
        //法一：递归算法
       /* if(root == null){
            return 0;
        }
        //深度
        int deepth=0;
        //最大值
        int max=0;
        getmaxDeepth(root,deepth,max);
        return max;*/

        //简化递归
       /* if(root==null){
            return 0;
        }
        return 1+Math.max(TreeDepth(root.left),TreeDepth(root.right));*/


        //法二：层序遍历的方法
        if(root==null){
            return 0;
        }
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.add(root);
        int deepth=0;
        while(!queue.isEmpty()){
            //获取队列中元素个数
            int size=queue.size();
            //队列不为空，说明是有一层的
            deepth++;
            for(int i=0;i<size;i++){
                TreeNode cur = queue.poll();//获取当前节点
                //判断弹出的节点左右子树是否为空，不为空的话就加入到队列里面
                if(cur.left!=null){
                    queue.offer(cur.left);
                }
                if(cur.right!=null){
                    queue.offer(cur.right);
                }
            }
        }
        return deepth;
    }
}
